package org.bjf.utils;

import com.google.common.graph.GraphBuilder;
import com.google.common.graph.MutableGraph;

import java.util.HashSet;
import java.util.Set;

/**
 * @author bjf on 2021/1/4.
 * @version 1.022222
 */
public class TestGraph {

    public static void main(String[] args) {
        MutableGraph<Integer> g = GraphBuilder
                //指定为有向图
                .directed()
                //允许自环
                .allowsSelfLoops(false)
                .build();


        g.addNode(4);
        g.addNode(1);
        g.addNode(2);
        g.addNode(3);
        g.addNode(6);
        g.addNode(5);
        g.addNode(8);
        g.addNode(7);

        g.putEdge(1, 2);
        g.putEdge(1, 3);
        g.putEdge(2, 4);
        g.putEdge(3, 4);
        g.putEdge(5, 3);
        g.putEdge(5, 6);
        g.putEdge(6, 3);
        g.putEdge(7, 8);
        System.out.println("g = " + g);

        while (!g.nodes().isEmpty()) {
            Set<Integer> rmNodes = new HashSet<>();
            for (Integer node : g.nodes()) {
                int inDegree = g.inDegree(node);
                if (inDegree == 0) {
                    rmNodes.add(node);
                }
            }
            for (Integer rmNode : rmNodes) {
                System.out.println(rmNode);
                g.removeNode(rmNode);
            }
            System.out.println(" =============wwwwww============== ");
        }
        /*for (Integer node : g.nodes()) {
            int inDegree = g.inDegree(node);
            if (inDegree == 0) {
                System.out.println(node);
            }
        }

        System.out.println(" =========================== ");
        g.removeNode(1);

        for (Integer node : g.nodes()) {
            int inDegree = g.inDegree(node);
            if (inDegree == 0) {
                System.out.println(node);
            }
        }*/
        /* List<Integer> curr = Arrays.asList(3,6,2,7);
         *//*MutableGraph<Integer> sugG = Graphs.inducedSubgraph(g, curr);
        System.out.println("sugG = " + sugG);*//*

        Set<Integer> subSet = new HashSet<>();
        for (Integer integer : curr) {
            Iterable<Integer> bfs = Traverser.forGraph(g).breadthFirst(integer);
            Set<Integer> sub = StreamSupport.stream(bfs.spliterator(), false).collect(Collectors.toSet());
            subSet.addAll(sub);
        }
         MutableGraph<Integer> sugG = Graphs.inducedSubgraph(g, subSet);
        System.out.println("sugG = " + sugG);

        List<Integer> zeroNodes = new ArrayList<>();
        for (Integer node : sugG.nodes()) {
            int inDegree = sugG.inDegree(node);
            if (inDegree == 0) {
                zeroNodes.add(node);
            }
        }
        Iterable<Integer> bfs = Traverser.forGraph(sugG).breadthFirst(zeroNodes);
        List<Integer> chain = StreamSupport.stream(bfs.spliterator(), false).collect(Collectors.toList());
        System.out.println("chain = " + chain);


        List<Integer> temp = Arrays.asList(7,3,1);
        List<Integer> actTemp = temp.stream().filter(chain::contains).collect(Collectors.toList());
        System.out.println("actTemp = " + actTemp);

        Graph<Integer> transpose = Graphs.transpose(sugG);
        System.out.println("transpose = " + transpose);


        List<Integer> aa = new ArrayList<>();
        for (Integer integer : actTemp) {
            Iterable<Integer> tempbfs = Traverser.forGraph(transpose).breadthFirst(integer);
            List<Integer> tempchain = StreamSupport.stream(tempbfs.spliterator(), false).collect(Collectors.toList());
            aa.addAll(tempchain);
        }
        List<Integer> sync = new ArrayList<>();
        List<Integer> async = new ArrayList<>();
        for (Integer integer : chain) {
            if (aa.contains(integer)) {
                sync.add(integer);
            } else {
                async.add(integer);
            }
        }
        System.out.println("sync = " + sync);
        System.out.println("async = " + async);


        Iterable<Integer> tempbfs = Traverser.forGraph(transpose).breadthFirst(Arrays.asList(3));
        List<Integer> tempchain = StreamSupport.stream(tempbfs.spliterator(), false).collect(Collectors.toList());
        System.out.println("tempchain = " + tempchain);
        
        

        *//*for (Integer node : g.nodes()) {
            Set<Integer> reachNodes = Graphs.reachableNodes(g, node);
            for (Integer sub : reachNodes) {
                if (sub.equals(node)) {
                    continue;
                }
                Set<Integer> subReachNodes = Graphs.reachableNodes(g, sub);
                if (subReachNodes.contains(node)) {
                    System.out.println("cycle = " + sub + ":" + node);
                    return;
                }
            }
        }*//*
         */


    }
}
